from collections import deque

# 树节点类
class TreeNode:
    def __init__(self, num: int, val: int) -> None:
        self.number = num
        self.value = val
        self.children = []

# 在树中寻找深度最小的目标节点
# 并返回其编号
def findNode(root: TreeNode, t: int) -> int:
    # 使用一个队列保存待搜索的节点
    queue = deque()
    queue.append(root)

    # BFS搜索
    while queue:
        # 从队列中取出当前树节点，进行下一步搜索
        parentNode = queue.popleft()

        # 进一步搜索它的所有子节点
        for child in parentNode.children:
            # BFS找到第一个答案便可以直接返回
            if child.value == t:
                return child.number
            # 将新找到的节点放入队列
            queue.append(child)

    # 若搜索完毕还未找到答案，说明无解
    return -1

# 构建树，返回根节点
def buildTree(parents: list[int], values: list[int]) -> TreeNode:
    n = len(parents)
    tree = []
    for i in range(n):
        tree.append(TreeNode(i + 1, values[i]))
        parentNum = parents[i]
        if parentNum > 0:
            parent = tree[parentNum - 1]
            parent.children.append(tree[i])
    return tree[0]

if __name__ == '__main__':
    parents = [-1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 7, 8, 9, 11]
    values = [9, 7, 4, 1, 6, 8, 2, 9, 8, 7, 6, 8, 2, 5]
    root = buildTree(parents, values)
    treeNum = findNode(root, 8)
    print("树节点查找答案为:", treeNum)